1. Field of the Disclosure
The present disclosure relates to a computation device and a computation method capable of easily solving an NP-complete problem mapped into the Ising model by easily solving the Ising model.
2. Discussion of the Background Art
The Ising model has been researched originally as a model of a magnetic material but recently it is paid attention as a model mapped in an NP-complete problem or the like. However, it is very difficult to solve the Ising model when the number of sites is large. Thus, a quantum annealing machine and a quantum adiabatic machine in which the Ising model is implemented are proposed.
In the quantum annealing machine, after Ising interaction and Zeeman energy are physically implemented, the system is sufficiently cooled so as to realize a ground state, and the ground state is observed, whereby the Ising model is solved. However, in a case where the number of sites is large, when the system is trapped into a metastable state in the process of being cooled, the life of the metastable state exponentially increases with respect to the number of sites, and accordingly, there is a problem in that the metastable state is not easily mitigated to the ground state.
In the quantum adiabatic machine, transverse magnetic field Zeeman energy is physically implemented, and then the ground state of only the transverse magnetic field Zeeman energy is realized by sufficiently cooling the system. Then, Ising interaction is physically implemented slowly, the ground state of the system that includes the Ising interaction and vertical magnetic field Zeeman energy is realized, and ground state is observed, whereby the Ising model is solved. However, when the number of sites is large, there is a problem in that the speed of physically implementing the Ising interaction needs to be exponentially decreased with respect to the number of sites.
In a case where the NP-complete problem or the like is mapped into an Ising model, and the Ising model is implemented as a physical spin system, there is a problem of a natural law that Ising interaction between sites that are physically located close to each other is high, and Ising interaction between sites that are physically located far from each other is low. The reason for this is that, in an artificial Ising model in which the NP-complete problem is mapped, there may be cases where Ising interaction between sites that are physically located close to each other is low, and Ising interaction between sites that are physically located far is high. The difficult in mapping into a natural spin system also makes it difficult to easily solve the NP-complete problem or the like.    Non-Patent Document 1: Tim Byrnes, Kai Yan, and Yoshihisa Yamamoto, Optimization using Bose-Einstein condensation and measurement-feedback circuits, [online], Jan. 26, 2010, arXiv.org, [searched on Jan. 11, 2011], the Internet <URL: http://arxiv.org/abs/0909.2530>
The configuration of an Ising model computation device that is disclosed in Non-Patent Document 1 for solving some of the above-described problems is illustrated in FIG. 1. The Ising model computation device is configured by Bose-Einstein condensing units B1, B2, and B3, spin measuring units D1, D2, and D3, a feedback control circuit F, and Ising interaction implementing units I1, I2, and I3.
The Bose-Einstein condensing units B1, B2, and B3 are systems in which almost all the Bose particles are in the ground state at a very low temperature and are configured by exciton polaritons included in semiconductor micro-cavities, neutral atoms each having an unpaired electron, or the like. The Bose-Einstein condensing units B1, B2, and B3 are applied with magnetic fields B1, B2, and B3 to be described later and are configured by Bose particles having mutually-different spin directions denoted by white circles and black circles illustrated in FIG. 1.
The spin measuring units D1, D2, and D3 output currents I1, I2, and I3 that are in proportion to sums of all the spins respectively included in the Bose-Einstein condensing units B1, B2, and B3. Here, a sum Si of all the spins inside each site is represented as below. Here, σi represents the spin of each Bose particle of each site, and N represents a total number of Bose particles of each site.
                              S          i                =                              ∑                          k              =              1                        N                    ⁢                      σ            i            k                                              [                  Expression          ⁢                                          ⁢          1                ]            
The feedback control circuit F receives the currents I1, I2, and I3 as inputs from the spin measuring units D1, D2, and D3 and outputs feedback signals to the Ising interaction implementing units I1, I2, and I3. The Ising interaction implementing units I1, I2, and I3 receives the feedback signals from the feedback control circuit F as inputs and applies magnetic fields B1, B2, and B3 to the Bose-Einstein condensing units B1, B2, and B3, respectively. Here, the magnetic fields B1, B2, and B3 are represented as below. In addition, Jij represents an Ising interaction coefficient between an i-th site and a j-th site, and M represents the number (three in FIG. 1) of all the sites.
                              B          i                =                              ∑                          j              =              1                        M                    ⁢                                    J              ij                        ⁢                          S              j                                                          [                  Expression          ⁢                                          ⁢          2                ]            
Hamiltonian H of all the Bose-Einstein condensing units B1, B2, and B3 is represented as below. In other words, the Ising interaction is implemented.
                    H        =                                            ∑                              i                =                1                            M                        ⁢                                          B                i                            ⁢                              S                i                                              =                                    ∑                              i                ,                                  j                  =                  1                                            M                        ⁢                                          J                ij                            ⁢                              S                i                            ⁢                              S                j                                                                        [                  Expression          ⁢                                          ⁢          3                ]            
When the Ising model computation device illustrated in FIG. 1 is applied as a quantum annealing machine, the problem that the system is not easily mitigated from the metastable state to the ground state can be partly solved. In other words, in a case where the mitigation rate from the metastable state to the ground state is A when the number of Bose particles occupying the ground state is zero, the mitigation rate increases to A(L+1) when the number of Bose particles occupying the ground state is L. Here, since L and N are of a same order, the computation time is shortened in inverse proportion to the number N of Bose particles.
When the Ising model computation device illustrated in FIG. 1 is applied as a quantum adiabatic machine, the problem that the speed of physically implementing the Ising interaction needs to be lowered step by step in accordance with an increase in the number of sites can be partly solved. In other words, even in a case where a change in Hamiltonian is too fast, and Bose particles leak from the ground state to an excited state, the Bose particles are returned from the excited state to the ground state by Bose-Einstein condensing, and error correction is made in proportion to the number N of Bose particles. Accordingly, the computation time is shortened in inverse proportion to the number N of Bose particles.
In the Ising model computation device illustrated in FIG. 1 can freely control not only the magnitude of Ising interaction between sites that are physically located close to each other but also the magnitude of Ising interaction between sites that are physically located far from each other through the feedback control circuit F. Accordingly, regardless of a physical distance between sites, an artificial Ising model mapped from an NP-complete problem can be solved.
In the Ising model computation device illustrated in FIG. 1, for N spins included in each site, it is determined whether one type of upward and downward spins is more than the other type based on the rule of majority. Thus, the temperature of the system is a finite temperature, and, accordingly, even when there is a spin leaking from the ground state to the excited state, the probability of acquiring a correct answer is markedly higher when the number of spins included in each site is N than that when the number of spins is one.
However, in the Ising model computation device illustrated in FIG. 1, the spin measuring units D1, D2, and D3 output currents I1, I2, and I3 that are respectively in proportion to sums of all the spins included in the Bose-Einstein condensing units B1, B2, and B3, and the feedback control circuit F receives the currents I1, I2, and I3 from the spin measuring units D1, D2, and D3 as inputs and outputs feedback signals to the Ising interaction implementing units I1, I2, and I3. In other words, for each feedback, quantum coherence of the whole system is broken, whereby the spin state of the whole system is determined.
Here, the determined spin state of the whole system is not limited to the ground state. Thus, the spin state of the whole system needs to be determined over and over until the spin state of the whole system is settled to the ground state, and, in a worst case, spin states of 2M kinds of the whole system need to be determined. In other words, the computation time is in proportion to 2M/N, and thus, even when Bose-Einstein condensing is applied, the exponential divergence of the computation time cannot be suppressed.
Thus, in order to solve the above-described problems, an object of the present disclosure is to provide a computation device and a computation method suppressing exponential divergence of the computation time of an NP-complete problem or the like mapped into an Ising model.